package h0804;

import java.util.Scanner;

/**
  * @description 5G网络建设
  * @author 不知名帅哥
  * @date 2024/8/4 22:38
  * @version 1.0
*/

//prim算法
public class FiveGNetworkConstruction {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int m=sc.nextInt();

        //邻接矩阵
        int[][] graph=new int[n+1][n+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j < n; j++) {
                //初始化默认各点之间互不连通，即i-j边权无限大
                graph[i][j]=Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < m; i++) {
            int x=sc.nextInt();
            int y=sc.nextInt();
            int z = sc.nextInt();
            int p = sc.nextInt();

            if (p==0){
                //x-y边权为z
                graph[x][y]=z;
                graph[x][y]=z;
            }else {
                //对应已经联通的两点，可以理解为边权为0
                graph[x][y]=0;
                graph[x][y]=0;
            }
        }

        System.out.println(prim(graph,n));
    }

    private static int prim(int[][] graph, int n) {
        //记录最小生成树的边权和
        int minWeight=0;

        //inTree[i]表示节点i是否在生成树中
        boolean[] inTree=new boolean[n+1];

        //初始时任选一个节点作为最小生成树的初始节点，这里选择节点1
        inTree[1]=true;
        //记录最小生成树中点的数量
        int inTree_count=1;

        //dis[i]表示节点i到最小生成树集合的最短距离
        int[] dis=new int[n+1];
        for (int i = 1; i <=n; i++) {
            //初始时，最小生成树集合中只有节点1，因此其他节点到最小生成树的距离，其实就是到节点1的距离
            dis[i]=graph[1][i];
        }
        //如果最小生成树中点的数量达到n个，则结束循环
        while (inTree_count<n){
            //我们现在要从未纳入最小生成树的点中，找到一个距离最小生成树最近的

            //minDis记录这个最近距离
            int minDis=Integer.MAX_VALUE;
            //idx记录距离最小生成树minDis个距离的节点
            int nodeIdx=0;

            for (int i = 1; i <= n; i++) {
                //从未纳入最小生成树的点中，找到一个距离最小生成树最近的
                if (!inTree[i]&&dis[i]<minDis){
                    minDis=dis[i];
                    nodeIdx=i;
                }
            }

            //如果nodeIdx==0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VAlUE,即不与最小生成树存在关联1
            if (nodeIdx==0){
                return -1;
            }

            inTree[nodeIdx]=true; //最小生成树需要纳入最短距离点nodeIdx
            inTree_count++; //最小生成树中点数量+1
            minWeight+=dis[nodeIdx];
        }

        return minWeight;
    }
}





















